class Solution
{
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { -1,1,0,0 };
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
    {
        int m = image.size(), n = image[0].size();
        queue<pair<int, int>> q;
        int prev = image[sr][sc];
        if (image[sr][sc] == color) return image;
        q.push({ sr,sc });
        image[sr][sc] = color;
        while (q.size())
        {
            int sz = q.size();
            for (int i = 0; i < sz; i++)
            {
                auto [a, b] = q.front();
                q.pop();
                for (int k = 0; k < 4; k++)
                {
                    int x = a + dx[k], y = b + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev)
                    {
                        image[x][y] = color;
                        q.push({ x,y });
                    }

                }
            }
        }
        return image;
    }
};